package countingBits;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int[] countBits(int num) {
        int[] result=new int[num+1];
        result[0]=0;
        if (num==0) return result;
        int t=1;
        Queue<Integer[]> q=new LinkedList<>();
        Integer[] one={1,1};
        q.add(one);
        while (q.isEmpty()==false){
        	int now=q.peek()[0];
        	int re=q.poll()[1];
        	result[now]=re;
        	if ((now<<1)+1<=num){
        		Integer[] temp={(now<<1)+1,re+1};
        		q.add(temp);
        	}
        	if ((now<<1)<=num){
        		Integer[] temp={(now<<1),re};
        		q.add(temp);
        	}
        }
        return result;
    }
    
    public int[] countBits_1(int num) {
        int[] f=new int[num+1];
        f[0]=0;
        if (num==0) return f;
        f[1]=1;
        int up=2;
        for (int i=2;i<=num;i++){
        	if (i>=up<<1) up=i;
        	f[i]=f[i-up]+1;
        }
        return f;
        		
    }
    
    public static void main(String args[]) {
		Solution so=new Solution();
		for (Integer t:so.countBits_1(5)){
			System.out.println(t);
		}
	}
}